home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Tree / Binary_Tree.h < prev    next >
C/C++ Source or Header  |  1992-07-01  |  9KB  |  205 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MBN 06/28/89 -- Initial design and implementation
  13. // Updated: MBN 09/15/89 -- Added conditional exception handling
  14. // Updated: DKM 11/05/89 -- Replaced cache traversal with stack traversal
  15. //                          Also added support for AVL balancing
  16. // Updated: LGO 12/04/89 -- operator<< not inline
  17. // Updated: MBN 12/21/89 -- Added optional argument to set_compare method
  18. // Updated: MBN 02/20/90 -- Cut operators <, >, <=, >=; fixed operators ==, !=
  19. // Updated: MJF 06/30/90 -- Added base class name to constructor initializer
  20. // Updated: VDN 02/21/92 -- New lite version
  21. //
  22. // The Binary_Tree<Type> class is publicly derived  from the  Binary_Tree class
  23. // and  implements simple, dynamic, sorted sequences.   Users requiring  a data
  24. // structure for  unsorted  sequences whose structure  and organization is more
  25. // under the control  of the programmer  are refered  to the N_Tree class.  The
  26. // Binary_Tree<Type>  class  is  a   friend   of the  Binary Node  class,  also
  27. // parameterized over the  same Type.  There is no  attempt made  to balance or
  28. // prune the tree.  Nodes  are added to  a particular sub-tree at the direction
  29. // of  the colating function.  As a  result, a tree parameterized  for integers
  30. // and that  uses the default integer  comparison operators whose  elements are
  31. // added in increasing order would result  in a lopsided  tree.  Likewise after
  32. // many items have been added and removed.
  33. //
  34. // The Binary_Tree<Type> class supports  the concept of  a current position  as
  35. // the tree is  traversed via  next, prev,  and find.   method that changes the
  36. // tree structure invalidates the current position state
  37. //
  38. // The  Binary_Tree<Type>  class supports   the concept of  a current position.
  39. // Once  the  current position is  initialized, the first  call  to advance the
  40. // current position causes an internal dynamic cache of pointers to nodes to be
  41. // created.  This cache is created by  an inorder traversal  of the tree. Other
  42. // current  position  advance and  decrement methods then  act  based  upon the
  43. // information in  the  cache.  Any  method  that changes  the  tree  structure
  44. // invalidates the cache.
  45. //
  46. // There are two  public constructors. The first takes  no arguments and simply
  47. // allocates initial storage for a  Binary_Tree<Type> object.  The second takes
  48. // a reference to an existing Binary_Tree<Type> object  and duplicates its size
  49. // and contents.  The Binary_Tree<Type> class has four private data slots.  The
  50. // first contains a pointer to the root of  the  tree, the second maintains the
  51. // current  position, the   third   contains a  pointer  to a  dynamic cache of
  52. // pointers to nodes used  by  the current  position  methods, and  the  fourth
  53. // contains a pointer  to the default  node comparison function.   In addition,
  54. // there are two private  methods.  The  first  is used  to create the cache of
  55. // pointers to nodes upon the first dispatch  to  advance the current position,
  56. // and the second is  the default  node  comparison function to  be used if the
  57. // user does not chose to provide one.
  58. //
  59. // Methods are available to put, remove, and find a node in a tree.  The reset,
  60. // next, prev, value,  remove, and find  methods provide a mechanism to iterate
  61. // through the nodes of  a tree based  upon the current position.  In addition,
  62. // all nodes can  be  removed from the  tree with  the clear method.  A balance
  63. // method is provided to allow  the user to shake the  tree at some appropriate
  64. // time in  order  to balance  the  left and  right  sub-trees.  This  might be
  65. // particularly useful in the case of static binary  trees, where the structure
  66. // becomes fixed and the impetus for fast, efficient searches is high. Finally,
  67. // the  equality, inequality,  less   than,  and greater  than    operators are
  68. // overloaded to provide node comparison functionality.
  69. //
  70.  
  71. #ifndef BINARY_TREEH                // If no definition for class
  72. #define BINARY_TREEH
  73.  
  74. #ifndef BASE_BINARY_TREEH            // If no definition for class
  75. #include <cool/Base_Binary_Tree.h>        // Include definition file
  76. #endif
  77.  
  78. #ifndef BINARY_NODEH                // If no definition for class
  79. #include <cool/Binary_Node.h>            // include definition file
  80. #endif
  81.  
  82. template <class Type> CoolBinary_Tree {
  83.   typedef int (*Type##_Tree_Compare)(const Type&, const Type&);
  84.   DECLARE CoolBinary_Node<Type>;
  85. }
  86.  
  87.  
  88. template <class Type>
  89. class CoolBinary_Tree<Type> : public CoolBinary_Tree {
  90. public:
  91.   CoolBinary_Tree<Type> ();                // Simple constructor
  92.   CoolBinary_Tree<Type> (const CoolBinary_Tree<Type>&);    // Copy constructor
  93.   ~CoolBinary_Tree<Type> ();                // Destructor 
  94.  
  95.   Boolean find (const Type&);            // Find value in tree
  96.  
  97.   Type& value ();                // Return value at current pos
  98.   inline CoolBinary_Node<Type>* get_root () const; // Return root node
  99.   inline CoolBinary_Node<Type>* node ();       // Return current node
  100.   inline Boolean remove ();            // Remove node at current pos
  101.   inline Boolean put (const Type&);        // Add value to tree 
  102.   inline Boolean remove (const Type&);        // Remove value from tree
  103.   CoolBinary_Tree<Type>& operator= (CoolBinary_Tree<Type>&); // Assignment operator
  104.   void balance ();                // Balance the tree
  105.  
  106.   void set_compare (Type##_Tree_Compare = NULL); // Set compare function
  107.   Boolean operator== (CoolBinary_Tree<Type>&);        // Overload equality
  108.   inline Boolean operator!= (CoolBinary_Tree<Type>&);    // Overload not equal
  109.  
  110.   friend ostream& operator<< (ostream&, const CoolBinary_Tree<Type>&);
  111.   inline friend ostream& operator<< (ostream&, const CoolBinary_Tree<Type>*);
  112.  
  113. protected:
  114.   Boolean put_internal    (const Type&, Boolean avl=NULL);// adds a node
  115.   Boolean remove_internal (const Type&, Boolean avl=NULL);// removes a node
  116.   inline CoolBinary_Node<Type>* copy_nodes(const CoolBinary_Node<Type>*) const; // Copy subnodes
  117.  
  118. private:
  119.   Type##_Tree_Compare compare;            // Compare function
  120.   CoolBinary_Node<Type>* baltree (long);    // Build balanced subtree
  121.   friend void Type##_print_tree (const CoolBinary_Node<Type>*, ostream&);
  122.   friend int Type##_default_node_compare (const Type&, const Type&);
  123. };
  124.  
  125.  
  126. // get_root -- return node that roots this tree
  127. // Input:      None
  128. // Output:     Pointer to CoolBinary_Node of type Type.
  129.  
  130. template <class Type>
  131. inline CoolBinary_Node<Type>* CoolBinary_Tree<Type>::get_root () const {
  132.   return (CoolBinary_Node<Type>*)CoolBinary_Tree::get_root ();
  133. }
  134.  
  135. // node -- return node pointed to by the current position
  136. // Input:      None
  137. // Output:     Pointer to CoolBinary_Node of type Type.
  138.  
  139. template <class Type>
  140. inline CoolBinary_Node<Type>* CoolBinary_Tree<Type>::node () {
  141.   return (CoolBinary_Node<Type>*)CoolBinary_Tree::node ();
  142. }
  143.  
  144. // put -- Add a value to the sorted binary tree if it is not already there
  145. // Input: Reference to value to add to tree
  146. // Output: TRUE if item added, FALSE otherwise
  147.  
  148. template <class Type>
  149. inline Boolean CoolBinary_Tree<Type>::put (const Type& value) {
  150.   return this->put_internal (value);
  151. }
  152.  
  153.  
  154. // remove -- Remove a value from the sorted binary tree. Deletion of a node
  155. //           that has both left and right subtrees is done by descending down 
  156. //           the rightmost branch of the left subtree of the element to be
  157. //           deleted until a leaf is encountered, at which point the change is
  158. //           propagated back.
  159. // Input:    Reference to value to remove
  160. // Output:   TRUE if item removed, FALSE otherwise
  161.  
  162. // For a Binary Tree, call remove_internal without the avl flag
  163. template <class Type>
  164. inline Boolean CoolBinary_Tree<Type>::remove (const Type& value) {
  165.   return this->remove_internal(value);
  166. }
  167.  
  168.  
  169. // remove -- Remove node at current position in the tree
  170. // Input:    None
  171. // Output:   Value of node removed from tree
  172.  
  173. template <class Type>
  174. inline Boolean CoolBinary_Tree<Type>::remove () {
  175.   return this->remove_internal (this->value());
  176. }
  177.  
  178.  
  179.  
  180. // operator<< -- Output a binary tree by printing it sideways where the root is
  181. //               printed at the left margin. To obtain the normal orientation,
  182. //               rotate the output 90 degrees clockwise
  183. // Input:        Reference to output stream, reference to CoolBinary_Tree<Type>
  184. // Output:       Reference to output stream
  185.  
  186. template <class Type> CoolBinary_Tree {
  187. inline ostream& operator<< (ostream& os, const CoolBinary_Tree<Type>* b) {
  188.   return os << *b;
  189. }
  190. }
  191.  
  192.  
  193. // operator!= -- Compare binary trees for different values and/or structure
  194. // Input:        constant reference to another binary tree
  195. // Output:       TRUE/FALSE
  196.  
  197. template <class Type>
  198. inline Boolean CoolBinary_Tree<Type>::operator!=(CoolBinary_Tree<Type>& t) {
  199.   return (! (*this == t));
  200. }
  201.  
  202. #endif                        // End BINARY_TREEH #if
  203.  
  204.  
  205.